package DoExercise.HSP_ZCY.A015_暴力递归;

/**
 * 给定两个长度都为N的数组weights和values，
 * weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，
 * 你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 * <p>
 * 从左到右的尝试模型
 */
public class Code07_背包问题
{
    
    public static void main(String[] args)
    {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(getMaxValue(weights, values, bag));
        System.out.println(maxValue(weights, values, bag));
    }
    
    public static int getMaxValue(int[] weight, int[] value, int bag)
    {
        return process(weight, value, 0, 0, bag);
    }
    
    /**
     * @param weight   重量数组 不变
     * @param value    价值数组 不变
     * @param index    货物的下标，每一次都考虑index向后的货物的最大价值
     * @param alreadyW 之前做的选择已经累积的负重
     * @param bag      袋子的总载重 不变
     * @return -1认为没有价值
     */
    public static int process(int[] weight, int[] value, int index, int alreadyW, int bag)
    {
        //base case，重量已经超了
        if (alreadyW > bag)
        {
            return -1;
        }
        // 重量没超，但是没货了，返回0
        if (index == weight.length)
        {
            return 0;
        }
        int p1 = process(weight, value, index + 1, alreadyW, bag);//没有要index位置的货物，因为alreadyW没变化
        int p2next = process(weight, value, index + 1, alreadyW + weight[index], bag);//要了index位置的货物
        int p2 = -1;
        if (p2next != -1)//计算p2的价值
        {
            p2 = value[index] + p2next;
        }
        return Math.max(p1, p2);
    }
    
    /**
     * @param weight
     * @param value
     * @param bag    剩余空间
     * @return
     */
    public static int maxValue(int[] weight, int[] value, int bag)
    {
        return process(weight, value, 0, bag);
    }
    
    /**
     * 只剩下rest的空间，index...货物自由选择，但是不要超过rest的空间，返回能够获得的最大价值
     *
     * @param weight
     * @param value
     * @param index
     * @param rest   剩余的空间
     * @return
     */
    public static int process(int[] weight, int[] value, int index, int rest)
    {
        if (rest <= 0)
        { // base case 1
            return -1;
        }
        // rest >=0
        if (index == weight.length)
        { // base case 2
            return 0;
        }
        // 有货也有空间
        int p1 = process(weight, value, index + 1, rest);
        int p2 = -1;
        int p2Next = process(weight, value, index + 1, rest - weight[index]);//之前货物的累加值
        if (p2Next != -1)
        {
            p2 = value[index] + p2Next;//当前位置的价值 + 之前货物的累加值
        }
        return Math.max(p1, p2);
    }
}
